# coding=utf-8
'''
六只青蛙跳石头的暴力解法
问题：
7块石头 和 6只青蛙，三只在左边的三块石头上(设为A)，另外三只在右边三块石头上（设为B），中间的石头是空的（设为O）。
这是初始状态。
现在需要青蛙跳动，使得左边三个和右边三个换位置，即有初始的（AAAOBBB）变成(BBBOAAA)。
跳动规则，青蛙只能跳到旁边的石头或者隔一只青蛙跳到石头上，且A青蛙只能向右跳，B青蛙只能向左跳。

解法：
将问题抽象成[A,A,A,o,B,B,B]向[B,B,B,O,A,A,A]的迁移问题，且把青蛙跳跃转换成O的“跳跃”，
O只能和左侧的A换位置，或者只能和右边的B换位置，只能和旁边的或隔一个元素的元素交换值。

故O的动作有四种，左1、左2、右1、右2
'''
class Stack:
    """模拟栈"""

    def __init__(self):
        self.items = []

    def isEmpty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        if not self.isEmpty():
            return self.items[len(self.items) - 1]

    def size(self):
        return len(self.items)

target = ['b', 'b', 'b', 'o', 'a', 'a', 'a']
 
def left(step: int, src: list, index: int):
    newindex = index - step
    if newindex >= 0 and src[newindex] == 'a':
        # 交换两个位置的值
        src[index] = 'a'
        src[newindex] = 'o'
        return newindex
    else:
        # 不可交换
        return index


def right(step: int, src: list, index: int):
    new_index = index + step
    # 右交换只能是B
    if new_index < len(src) and src[new_index] == 'b':
        # 交换两个位置的值
        # tmp = src[index]
        src[index] = 'b'
        src[new_index] = 'o'
        return new_index
    else:
        # 不可交换
        return index


def jump(original: list, index: int, history: Stack, visited=[]):
    # print('list:' + str(original))
    # print('visited:' + str(visited))
    if original == target:
        print("ok：" + str(original))
        print('stack:')
        for i in history.items:
            print(i)
        return original
    if original in visited:
        return original
    visited.append(original.copy())
    history.push(original.copy())
    # 左1
    src = original.copy()
    new_index = left(1, src, index)
    if new_index != index:
        jump(src, new_index, history, visited)
    # 左2 
    src = original.copy()
    new_index = left(2, src, index)
    if new_index != index:
        jump(src, new_index, history, visited)
    # 右1
    src = original.copy()
    new_index = right(1, src, index)
    if new_index != index:
        jump(src, new_index, history, visited)
    # 右2
    src = original.copy()
    new_index = right(2, src, index)
    if new_index != index:
        jump(src, new_index, history, visited)
    # 四种动作均尝试后，均无结果
    history.pop()
    # print('return')


def main():
    visited = []
    original = ['a', 'a', 'a', 'o', 'b', 'b', 'b']
    jump(original, 3, Stack(), visited)
    print('visited:',end='')
    print(visited)


if __name__ == '__main__':
    main()
     
